import java.util.PriorityQueue;

/*
 * @author zzr
 * @date: 2025/10/19  19:05
 * @description: Top - K 问题：求数据集中前 K 个最大 / 最小的元素
 * 如果求前 K 个最小的元素，可以创建一个容量为 K 的大根据，然后先添加 K 个元素进入这个大根堆
 * 然后将剩下的元素，与大根堆中的堆顶元素进行比较。如果当前元素比堆顶元素小
 * （因为是大根堆，堆顶元素是整个堆中最大的元素）
 * 则将堆顶元素出队，然后将当前元素进行入队操作
 */
public class Demo36 {

    /**
     * 求先 K 个最大的数据
     * @param array
     * @param k
     * @return
     */
    public int[] maxLestK(int[] array, int k) {

        int[] ret = new int[k];
        if (array == null || k < 0) {
            return ret;
        }

        // 建立一个容量为 K 的小根堆
        // PriorityQueue 默认实现就是小根堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k);

        // 先将 k 个元素放入小根堆中
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(array[i]);
        }
        // 剩余元素与栈顶元素比较
        // 注意此时循环的开始值为 k
        for (int i = k; i < array.length; i++) {

            int top = priorityQueue.peek();
            if (array[i] > top) {
                priorityQueue.poll();
                priorityQueue.offer(array[i]);
            }

        }

        // 小根堆中 k 个元素就是要求的 前 K 个最大元素~
        for (int i = 0; i < k; i++) {
            Integer poll = priorityQueue.poll();
            ret[i] = poll;
        }
        return ret;
    }
}
